<?php
/**
 * User: helloJiu
 * Date: 2021/9/26
 * Time: 15:38
 */

namespace App\Algorithm\DP;


class LengthOfLIS
{
    /**
     * 求最长递增上升子序列
     * 使用动态规划求解
     * [0,1,0,3,2,3]
     * [10,9,2,5,3,7,101,18]
     * https://leetcode-cn.com/problems/longest-increasing-subsequence/
     * @param int[] $nums
     * @return int
     */
    function lengthOfLIS($nums)
    {
        // $dp[$i] 表示$i结尾最长上升子序列长度
        $dp = [];
        $dp[0] = 1;
        for ($i = 0; $i < count($nums); $i++) {
            $v = $nums[$i];
            $dp[$i] = 1;
            for($j = $i-1; $j>=0; $j--){
                if($nums[$j] < $v && $dp[$i] < $dp[$j] + 1){
                    $dp[$i] = $dp[$j] + 1;
                }
            }
        }
        return max($dp);
    }
}